package com.mamingchao.issue.hash;

/**
 * 岛问题
 【题目】
 一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右四个位置相连,如
 果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
 【举例】
 001010
 111010
 100100
 000000
 这个矩阵中有三个岛
 【进阶】
 如何设计一个并行算法解决这个问题
 * Created by mlamp on 2024/11/4.
 */
public class IslandIssue {

    private int countIsland(int[][] matrix){

        if (matrix == null || matrix[0] == null)
            return 0;

        // 行长度
        int rowNum = matrix.length;
        // 列长度
        int columnNum = matrix[0].length;
        int result = 0;

        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < columnNum; j++) {
                if (matrix[i][j] == 1){
                    result ++;
                    infect(matrix, i, j, rowNum, columnNum);
                }
            }
        }

        return  result;
    }

    /**
     *
     * @param matrix 原始的矩阵二位数组
     * @param i 行 号
     * @param j 列 号
     * @param rowNum 二维数组，行数
     * @param columnNum 二维数组，列数
     */
    private void infect(int[][] matrix, int i, int j, int rowNum, int columnNum) {
        // base case
        if (i <0 | i > rowNum | j <0 | j>columnNum | matrix[i][j] !=1) {
            return;
        }

        infect(matrix,  i+1, j, rowNum, columnNum);
        infect(matrix,  i, j+1, rowNum, columnNum);
        infect(matrix,  i-1, j, rowNum, columnNum);
        infect(matrix,  i, j-1, rowNum, columnNum);
    }
}
